package cn.genmer.test.security.algorithm.sort;

/**
 * @description: 希尔排序
 * @author: Genmer
 * @create: 2021-07-13 22:54
 **/
public class ShellSort {
    public static void main(String[] args) {
        int[] a = { 9,1,5,6,2,3 };
//        int[] sorted = sort(a);
//        System.out.println(Arrays.toString(sorted));
    }

    /**
     * 希尔排序
     * @param arr
     */
    public static void sort(int[] arr){
        int size = arr.length;
        int count = 0;
        for (int grap = size >> 1; grap>0; grap /= 2){
            for (int i = 0; i < size; i++) {
                for (int j = i; j > grap-1; j -= grap) {
                    if (arr[j] < arr[j-grap]){
                        count++;
                        swap(arr,j, j-grap);
                    }

                }
            }
        }
        System.out.println(count);
    }

    /**
     * 希尔排序 - Knuth序列
     * @param arr
     */
    public static void sort1(int[] arr){
        int count = 0;
        int size = arr.length;
        int h = 1;
        while (h <= size/3){
            h = h*3+1;
        }


        for (int grap =h; grap>0; grap = (grap-1) /3){
            for (int i = 0; i < size; i++) {
                for (int j = i; j > grap-1; j -= grap) {
                    if (arr[j] < arr[j-grap]){
                        count++;
                        swap(arr,j, j-grap);
                    }
                }
            }
        }
        System.out.println(count);
    }

    /**
     * 希尔排序 - Knuth序列
     * @param arr
     */
    public static void sortTest(int[] arr){
        int size = arr.length;
        int grep = 1;
        while (grep <= size/3){
            grep = grep*3 +1;
        }

        for (; grep>0; grep = (grep-1)/3){
            for (int i = 0; i < size; i++) {
                for (int j = i; j > grep-1; j -= grep) {
                    if (arr[j] < arr[j-grep]) swap(arr, j, j-grep);
                }
            }
        }
    }


    private static void swap(int[] arr, int pos1, int pos2){
        int temp = arr[pos1];
        arr[pos1] = arr[pos2];
        arr[pos2] = temp;
    }
}
